package fun.coding.leetcode;

public class DecodeWays {

	/**
	 * 30 -> 0
	 * 03 -> 0
	 * @param args
	 */
	public static void main(String[] args) {
		DecodeWays d = new DecodeWays();
		System.out.println(d.numDecodings("126"));
		System.out.println(d.numDecodings1("30"));
	}
	
	public int numDecodings(String s) {
		if (s == null || s.isEmpty()) return 0;
		
		int[] sol = new int[s.length() + 1];
		sol[0] = 1;
		// There could be leading 0s
		sol[1] = Integer.valueOf(s.substring(0, 1)) != 0 ? 1 : 0;
		
		for (int i = 2; i <= s.length(); ++i) {
			if (Integer.valueOf(s.substring(i-1, i)) != 0) {
				sol[i] = sol[i-1];
			}
			
			int twoDigits = Integer.valueOf(s.substring(i-2, i));
			if (twoDigits >= 10 && twoDigits <= 26) {
				sol[i] += sol[i-2];
			}
		}
		
		// if this value is not calculated, it will default 0
		return sol[s.length()];
	}
	
	  public int numDecodings1(String s) {
	        if (s == null || s.length() == 0) {
	            return 0;
	        }
	        int[] nums = new int[s.length() + 1];
	        nums[0] = 1;
	        nums[1] = s.charAt(0) != '0' ? 1 : 0;
	        for (int i = 2; i <= s.length(); i++) {
	            if (s.charAt(i - 1) != '0') {
	                nums[i] = nums[i - 1];
	            }
	            
	            int twoDigits = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
	            if (twoDigits >= 10 && twoDigits <= 26) {
	                nums[i] += nums[i - 2];
	            }
	        }
	        
	        return nums[s.length()];
	    }
}
